package com.leetcode;

public class BuySellStock3 {
	public int maxProfit(int[] prices) {
		int N = prices.length;
		if (N == 0) return 0;

		int[] forward = new int[N];
		int[] backward = new int[N];
		int max = 0;
        int low = prices[0];
        
        forward[0] = 0;
        for (int i=1; i<N; i++) {
        	if (prices[i] <= low) {
        		low = prices[i];
        	}
        	else {
        		max = Math.max(max, prices[i] - low);
        	}
        	forward[i] = max;
        }
        
        max = 0;
        backward[N-1] = 0;
        int high = prices[N-1];
        for (int i=N-2; i>=0; i--) {
        	if (prices[i] >= high) {
        		high = prices[i];
        	}
        	else {
        		max = Math.max(max, high - prices[i]);
        	}
        	backward[i] = max;
        }
        
        max = forward[N-1];
        for (int i=0; i<N-1; i++) {
        	max = Math.max(max, forward[i] + backward[i+1]);
        }
        
        return max;
    }
}
